/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void _recoverTree(TreeNode* root, TreeNode*& tar1, TreeNode*& tar2, TreeNode* nodeMin, TreeNode* nodeMax)
    {
        if (root == nullptr)
            return;
        int lower, upper;
        if (nodeMin)
            lower = nodeMin->val;
        else
            lower = INT_MIN;
        if (nodeMax)
            upper = nodeMax->val;
        else
            upper = INT_MAX;


        _recoverTree(root->left, tar1, tar2, nodeMin, root);
        if (root->val <= lower)
        {
            tar1 = nodeMin;
            tar2 = root;
            int tmp = tar1->val;
            tar1->val = tar2->val;
            tar2->val = tmp;


        }
        else if (root->val >= upper)
        {
            tar1 = nodeMax;
            tar2 = root;
            int tmp = tar1->val;
            tar1->val = tar2->val;
            tar2->val = tmp;

        }
        _recoverTree(root->right, tar1, tar2, root, nodeMax);
    }
    void recoverTree(TreeNode* root) {
        TreeNode* tar1 = nullptr;
        TreeNode* tar2 = nullptr;
        TreeNode* nodeMin = nullptr;
        TreeNode* nodeMax = nullptr;
        _recoverTree(root, tar1, tar2, nodeMin, nodeMax);

    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void _recoverTree(TreeNode* root, vector<TreeNode*>& v)
    {
        if (root == nullptr)
            return;
        _recoverTree(root->left, v);
        v.push_back(root);
        _recoverTree(root->right, v);
    }
    void recoverTree(TreeNode* root) {
        vector<TreeNode*> v;
        _recoverTree(root, v);
        int front = 0;
        int back = v.size() - 1;
        for (int i = 0; i <= back - 1; i++)
        {
            for (int j = i + 1; j <= back; j++)
            {
                if (v[j]->val < v[i]->val)
                {
                    int tmp = v[j]->val;
                    v[j]->val = v[i]->val;
                    v[i]->val = tmp;
                }
            }
        }

    }
};